/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/
#include "qbsp.h"


/*

  Lightmap allocation has to be done after all flood filling and
  visible surface determination.

*/

int					numSortShaders;
mapDrawSurface_t	*surfsOnShader[MAX_MAP_SHADERS];


int		allocated[LIGHTMAP_WIDTH];

int		numLightmaps = 0;
int		c_exactLightmap;
int		samplesize = 8;
int		numLightTexels = 0;

typedef struct lightmapTreeNode_s
{
	int x, y, w, h;
	int subW, subH;
	struct lightmapTreeNode_s *children[2];
	qboolean occupied;
} lightmapTreeNode_t;

typedef struct lightmapTreeLink_s
{
	int lmID;
	lightmapTreeNode_t *headNode;

	struct lightmapTreeLink_s *next;
} lightmapListLink_t;

static lightmapListLink_t *lightmapList = NULL;

// Based on "Packing Lightmaps" http://www.blackpawn.com/texts/lightmaps/default.html
lightmapTreeNode_t *InsertLightmapIntoNode(lightmapTreeNode_t *node, int w, int h)
{
	lightmapTreeNode_t *subNode;
	int dw, dh;

	if(node->children[0])
	{
		// Split node, try inserting into children
		subNode = InsertLightmapIntoNode(node->children[0], w, h);
		if(subNode) return subNode;
		return InsertLightmapIntoNode(node->children[1], w, h);
	}

	// Leaf node
	if(node->occupied) return NULL;		// Already a lightmap in this leaf

	if(node->w < w || node->h < h) return NULL;	// Doesn't fit

	if(node->w == w && node->h == h) return node;	// Fits perfectly

	// Imperfect fit, create children
	node->children[0] = malloc(sizeof(lightmapTreeNode_t));
	memset(node->children[0], 0, sizeof(lightmapTreeNode_t));
	node->children[1] = malloc(sizeof(lightmapTreeNode_t));
	memset(node->children[1], 0, sizeof(lightmapTreeNode_t));

	dw = node->w - w;
	dh = node->h - h;

	if(dw > dh)
	{
		// Split vertically
		node->children[0]->x = node->x;
		node->children[0]->y = node->y;
		node->children[0]->w = w;
		node->children[0]->h = node->h;

		node->children[1]->x = node->x + w;
		node->children[1]->y = node->y;
		node->children[1]->w = node->w - w;
		node->children[1]->h = node->h;
	}
	else
	{
		// Split horizontally
		node->children[0]->x = node->x;
		node->children[0]->y = node->y;
		node->children[0]->w = node->w;
		node->children[0]->h = h;

		node->children[1]->x = node->x;
		node->children[1]->y = node->y + h;
		node->children[1]->w = node->w;
		node->children[1]->h = node->h - h;
	}

	// Insert into the first one
	return InsertLightmapIntoNode(node->children[0], w, h);
}

qboolean AllocLMBlock2 (int w, int h, int *x, int *y)
{
	lightmapTreeNode_t *node = InsertLightmapIntoNode(lightmapList->headNode, w, h);

	if(!node) return qfalse;

	// This node's occupied now
	node->occupied = qtrue;

	// Get coords
	*x = node->x;
	*y = node->y;

	return qtrue;
}

void PrepareNewLightmap2( void )
{
	lightmapListLink_t *lmTree = malloc(sizeof(lightmapListLink_t));

	lmTree->lmID = numLightmaps;

	lmTree->headNode = malloc(sizeof(lightmapTreeNode_t));
	lmTree->headNode->occupied = qfalse;
	lmTree->headNode->x = lmTree->headNode->y = 0;
	lmTree->headNode->w = LIGHTMAP_WIDTH;
	lmTree->headNode->h = LIGHTMAP_HEIGHT;
	lmTree->headNode->children[0] = lmTree->headNode->children[1] = NULL;
	lmTree->next = lightmapList;

	lightmapList = lmTree;

	numLightmaps+=MAP_BASIS_VECTORS;
}


void PrepareNewLightmap( void ) {
	memset( allocated, 0, sizeof( allocated ) );
	numLightmaps+=MAP_BASIS_VECTORS;
}

/*
===============
AllocLMBlock

returns a texture number and the position inside it
===============
*/
qboolean AllocLMBlock (int w, int h, int *x, int *y)
{
	int		i, j;
	int		best, best2;

	best = LIGHTMAP_HEIGHT;

	for ( i=0 ; i <= LIGHTMAP_WIDTH-w ; i++ ) {
		best2 = 0;

		for (j=0 ; j<w ; j++) {
			if (allocated[i+j] >= best) {
				break;
			}
			if (allocated[i+j] > best2) {
				best2 = allocated[i+j];
			}
		}
		if (j == w)	{	// this is a valid spot
			*x = i;
			*y = best = best2;
		}
	}

	if (best + h > LIGHTMAP_HEIGHT) {
		return qfalse;
	}

	for (i=0 ; i<w ; i++) {
		allocated[*x + i] = best + h;
	}

	return qtrue;
}


/*
===================
AllocateLightmapForPatch
===================
*/
//#define LIGHTMAP_PATCHSHIFT

void AllocateLightmapForPatch( mapDrawSurface_t *ds ) {
	int			i, j, k;
	drawVert_t	*verts;
	int			w, h;
	int			x, y;
	float		s, t;
	mesh_t		mesh, *subdividedMesh, *tempMesh, *newmesh;
	int			widthtable[LIGHTMAP_WIDTH], heighttable[LIGHTMAP_HEIGHT], ssize;
	float		wRescale, hRescale;

	verts = ds->verts;

	mesh.width = ds->patchWidth;
	mesh.height = ds->patchHeight;
	mesh.verts = verts;
	newmesh = SubdivideMesh( mesh, 8, 999 );

	PutMeshOnCurve( *newmesh );
	tempMesh = RemoveLinearMeshColumnsRows( newmesh );
	FreeMesh(newmesh);

	ssize = samplesize;
	if (ds->shaderInfo->lightmapSampleSize)
		ssize = ds->shaderInfo->lightmapSampleSize;

#ifdef LIGHTMAP_PATCHSHIFT
	subdividedMesh = SubdivideMeshQuads( tempMesh, ssize, LIGHTMAP_WIDTH-1, widthtable, heighttable);
#else
	subdividedMesh = SubdivideMeshQuads( tempMesh, ssize, LIGHTMAP_WIDTH, widthtable, heighttable);
#endif

	w = subdividedMesh->width;
	h = subdividedMesh->height;

#ifdef LIGHTMAP_PATCHSHIFT
	w++;
	h++;
#endif

	FreeMesh(subdividedMesh);

	// allocate the lightmap
	c_exactLightmap += w * h * MAP_BASIS_VECTORS;

	if ( !AllocLMBlock2( w, h, &x, &y ) ) {
		PrepareNewLightmap2();
		if ( !AllocLMBlock2( w, h, &x, &y ) ) {
			Error("Entity %i, brush %i: Lightmap allocation failed", 
				ds->mapBrush->entitynum, ds->mapBrush->brushnum );
		}
	}

#ifdef LIGHTMAP_PATCHSHIFT
	w--;
	h--;
#endif

	// set the lightmap texture coordinates in the drawVerts
	ds->lightmapNum = numLightmaps - MAP_BASIS_VECTORS;
	ds->lightmapWidth = w;
	ds->lightmapHeight = h;
	ds->lightmapX = x;
	ds->lightmapY = y;

	wRescale = ((float)(w-1)) / ((float)w);
	hRescale = ((float)(h-1)) / ((float)h);

	for ( i = 0 ; i < ds->patchWidth ; i++ ) {
		for ( k = 0 ; k < w ; k++ ) {
			if ( originalWidths[k] >= i ) {
				break;
			}
		}
		if (k >= w)
			k = w-1;
		//s = x + k;
		s = x + (wRescale * (float)k);

		for ( j = 0 ; j < ds->patchHeight ; j++ ) {
			for ( k = 0 ; k < h ; k++ ) {
				if ( originalHeights[k] >= j ) {
					break;
				}
			}
			if (k >= h)
				k = h-1;
			//t = y + k;
			t = y + (hRescale * (float)k);
			verts[i + j * ds->patchWidth].lightmap[0] = ( s + 0.5 ) / LIGHTMAP_WIDTH;
			verts[i + j * ds->patchWidth].lightmap[1] = ( t + 0.5 ) / LIGHTMAP_HEIGHT;
		}
	}
}


/*
===================
AllocateLightmapForSurface
===================
*/
//#define	LIGHTMAP_BLOCK	16
void AllocateLightmapForSurface( mapDrawSurface_t *ds ) {
	vec3_t		mins, maxs, size, exactSize, exactMins, exactMaxs, delta;
	int			i;
	drawVert_t	*verts;
	int			w, h;
	int			x, y, ssize;
	int			axis, sAxis, tAxis;
	vec3_t		vecs[2];
	float		s, t;
	vec3_t		origin;
	plane_t		*plane;
	float		d;
	float		scalar;
	vec3_t		planeNormal;

	if ( ds->lightmappedModel ) {
		return;		// Done during loading
	}

	if ( ds->patch ) {
		AllocateLightmapForPatch( ds );
		return;
	}

	ssize = samplesize;
	if (ds->shaderInfo->lightmapSampleSize)
		ssize = ds->shaderInfo->lightmapSampleSize;

	plane = &mapplanes[ ds->side->planenum ];

	// bound the surface
	ClearBounds( mins, maxs );
	verts = ds->verts;
	for ( i = 0 ; i < ds->numVerts ; i++ ) {
		AddPointToBounds( verts[i].xyz, mins, maxs );
	}

	// round to the lightmap resolution
	for ( i = 0 ; i < 3 ; i++ ) {
		exactSize[i] = maxs[i] - mins[i];
		exactMins[i] = mins[i];
		exactMaxs[i] = maxs[i];
		mins[i] = ssize * floor( mins[i] / ssize );
		maxs[i] = ssize * ceil( maxs[i] / ssize );
		size[i] = (maxs[i] - mins[i]) / ssize + 1;
	}


	// the two largest axis will be the lightmap size
	memset( vecs, 0, sizeof( vecs ) );

	planeNormal[0] = fabs( plane->normal[0] );
	planeNormal[1] = fabs( plane->normal[1] );
	planeNormal[2] = fabs( plane->normal[2] );

	if ( planeNormal[0] >= planeNormal[1] && planeNormal[0] >= planeNormal[2] ) {
		w = size[1];
		h = size[2];
		axis = 0;
		sAxis = 1;
		tAxis = 2;
		vecs[0][1] = 1.0;
		vecs[1][2] = 1.0;
	} else if ( planeNormal[1] >= planeNormal[0] && planeNormal[1] >= planeNormal[2] ) {
		w = size[0];
		h = size[2];
		axis = 1;
		sAxis = 0;
		tAxis = 2;
		vecs[0][0] = 1.0;
		vecs[1][2] = 1.0;
	} else {
		w = size[0];
		h = size[1];
		axis = 2;
		sAxis = 0;
		tAxis = 1;
		vecs[0][0] = 1.0;
		vecs[1][1] = 1.0;
	}

	// Round up to cluster size
	w += LIGHTMAP_CLUSTER_SIZE - 1;
	w -= w % LIGHTMAP_CLUSTER_SIZE;
	h += LIGHTMAP_CLUSTER_SIZE - 1;
	h -= h % LIGHTMAP_CLUSTER_SIZE;

#define NEWLIGHTVECS

#ifndef NEWLIGHTVECS
	VectorScale(vecs[0], (1.0 / ssize), vecs[0]);
	VectorScale(vecs[1], (1.0 / ssize), vecs[1]);

	if ( !plane->normal[axis] ) {
		Error( "Chose a 0 valued axis" );
	}

	if ( w > LIGHTMAP_WIDTH ) {
		VectorScale ( vecs[0], (float)LIGHTMAP_WIDTH/w, vecs[0] );
		w = LIGHTMAP_WIDTH;
	}
	
	if ( h > LIGHTMAP_HEIGHT ) {
		VectorScale ( vecs[1], (float)LIGHTMAP_HEIGHT/h, vecs[1] );
		h = LIGHTMAP_HEIGHT;
	}
#else
	if ( w > LIGHTMAP_WIDTH )
		w = LIGHTMAP_WIDTH;
	if ( h > LIGHTMAP_WIDTH )
		h = LIGHTMAP_WIDTH;

	scalar = (float)(w-1) / exactSize[sAxis];
	VectorScale(vecs[0], scalar, vecs[0]);
	scalar = (float)(h-1) / exactSize[tAxis];
	VectorScale(vecs[1], scalar, vecs[1]);
#endif

	c_exactLightmap += w * h;

	if ( !AllocLMBlock2( w, h, &x, &y ) ) {
		PrepareNewLightmap2();
		if ( !AllocLMBlock2( w, h, &x, &y ) ) {
			Error("Entity %i, brush %i: Lightmap allocation failed", 
				ds->mapBrush->entitynum, ds->mapBrush->brushnum );
		}
	}

	// set the lightmap texture coordinates in the drawVerts
	ds->lightmapNum = numLightmaps - MAP_BASIS_VECTORS;
	ds->lightmapWidth = w;
	ds->lightmapHeight = h;
	ds->lightmapX = x;
	ds->lightmapY = y;

	for ( i = 0 ; i < ds->numVerts ; i++ ) {
#ifndef NEWLIGHTVECS
		VectorSubtract( verts[i].xyz, mins, delta );
#else
		VectorSubtract( verts[i].xyz, exactMins, delta );
#endif
		s = DotProduct( delta, vecs[0] ) + x + 0.5;
		t = DotProduct( delta, vecs[1] ) + y + 0.5;
		verts[i].lightmap[0] = s / LIGHTMAP_WIDTH;
		verts[i].lightmap[1] = t / LIGHTMAP_HEIGHT;
	}

	// calculate the world coordinates of the lightmap samples

	// project mins onto plane to get origin
#ifndef NEWLIGHTVECS
	d = DotProduct( mins, plane->normal ) - plane->dist;
	d /= plane->normal[ axis ];
	VectorCopy( mins, origin );
	origin[axis] -= d;

	// project stepped lightmap blocks and subtract to get planevecs
	for ( i = 0 ; i < 2 ; i++ ) {
		vec3_t	normalized;
		float	len;

		len = VectorNormalize( vecs[i], normalized );
		VectorScale( normalized, (1.0/len), vecs[i] );
		d = DotProduct( vecs[i], plane->normal );
		d /= plane->normal[ axis ];
		vecs[i][axis] -= d;
	}
#else
	d = DotProduct( exactMins, plane->normal ) - plane->dist;
	d /= plane->normal[ axis ];
	VectorCopy( exactMins, origin );
	origin[axis] -= d;

	// project stepped lightmap blocks and subtract to get planevecs
	for ( i = 0 ; i < 2 ; i++ ) {
		vec3_t	normalized;
		float	len;

		len = VectorNormalize( vecs[i], normalized );
		VectorScale( normalized, (1.0/len), vecs[i] );
		d = DotProduct( vecs[i], plane->normal );
		d /= plane->normal[ axis ];
		vecs[i][axis] -= d;
	}
#endif

	VectorCopy( origin, ds->lightmapOrigin );
	VectorCopy( vecs[0], ds->lightmapVecs[0] );
	VectorCopy( vecs[1], ds->lightmapVecs[1] );
	VectorCopy( plane->normal, ds->lightmapVecs[2] );
}

/*
===================
AllocateLightmaps
===================
*/
void AllocateLightmaps( entity_t *e ) {
	int				i, j;
	mapDrawSurface_t	*ds;
	shaderInfo_t	*si;

	qprintf ("--- AllocateLightmaps ---\n");


	// sort all surfaces by shader so common shaders will usually
	// be in the same lightmap
	numSortShaders = 0;

	for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
		ds = &mapDrawSurfs[i];
		if ( !ds->numVerts ) {
			continue;		// leftover from a surface subdivision
		}
		if ( ds->miscModel && !ds->lightmappedModel ) {
			continue;
		}
		if ( !ds->patch && !ds->miscModel ) {
			VectorCopy( mapplanes[ds->side->planenum].normal, ds->lightmapVecs[2] );
		}

		// search for this shader
		for ( j = 0 ; j < numSortShaders ; j++ ) {
			if ( ds->shaderInfo == surfsOnShader[j]->shaderInfo ) {
				ds->nextOnShader = surfsOnShader[j];
				surfsOnShader[j] = ds;
				break;
			}
		}
		if ( j == numSortShaders ) {
			if ( numSortShaders >= MAX_MAP_SHADERS ) {
				Error( "MAX_MAP_SHADERS" );
			}
			surfsOnShader[j] = ds;
			numSortShaders++;
		}
	}
	qprintf( "%5i unique shaders\n", numSortShaders );

	// for each shader, allocate lightmaps for each surface

	PrepareNewLightmap2();

	for ( i = 0 ; i < numSortShaders ; i++ ) {
		si = surfsOnShader[i]->shaderInfo;

		for ( ds = surfsOnShader[i] ; ds ; ds = ds->nextOnShader ) {
			// some surfaces don't need lightmaps allocated for them
			if ( si->surfaceFlags & SURF_NOLIGHTMAP ) {
				ds->lightmapNum = -1;
			} else if ( si->surfaceFlags & SURF_POINTLIGHT ) {
				ds->lightmapNum = -3;
			} else {
				AllocateLightmapForSurface( ds );
			}
		}
	}

	qprintf( "%7i exact lightmap texels\n", c_exactLightmap );
	qprintf( "%7i block lightmap texels\n", numLightmaps * LIGHTMAP_WIDTH*LIGHTMAP_HEIGHT );
}

// Negative = a ... b
// Positive = b ... a
static int surfSort(const void *a, const void *b)
{
	const dsurface_t **dsap = (const dsurface_t **)a;
	const dsurface_t **dsbp = (const dsurface_t **)b;

	const dsurface_t *dsa = *dsap;
	const dsurface_t *dsb = *dsbp;

	// Surfaces with actual lightmaps are earlier
	if(dsa->lightmapNum < 0 && dsb->lightmapNum >= 0) return 1;
	if(dsb->lightmapNum < 0 && dsa->lightmapNum >= 0) return -1;
	if(dsa->lightmapNum < 0 && dsb->lightmapNum < 0) return 0;	// Both are invalid

	// Sort by shader
	if(dsa->shaderNum != dsb->shaderNum) return dsa->shaderNum - dsb->shaderNum;

	// Sort by order in the draw list
	return dsa - dsb;
}

void RechartLightmaps(void (*getDimensions)(int surfNum, int *w, int *h))
{
	dsurface_t **surfs;
	dsurface_t *surf;
	int i, j, numVerts;
	float rescaledCoord[2];
	float divisors[2];
	float multipliers[2];
	int newX, newY, newW, newH;

	qprintf ("--- RechartLightmaps ---\n");

	// Re-sort surfaces
	surfs = malloc(sizeof(dsurface_t *) * numDrawSurfaces);

	for(i=0;i<numDrawSurfaces;i++)
		surfs[i] = drawSurfaces + i;

	qsort(surfs, numDrawSurfaces, sizeof(dsurface_t *), surfSort);

	numLightmaps = 0;
	PrepareNewLightmap2();

	for(i=0;i<numDrawSurfaces;i++)
	{
		surf = surfs[i];

		if(surf->surfaceType == MST_PATCH)
			numVerts = surf->patchWidth * surf->patchHeight;
		else if(surf->surfaceType == MST_PLANAR)
			numVerts = surf->numVerts;
		else
			numVerts = 0;

		divisors[0] = surf->lightmapWidth - 1;
		divisors[1] = surf->lightmapHeight - 1;

		for(j=0;j<2;j++)
			if(divisors[j] <= 0.0f)
				divisors[j] = 1.0f;

		if(surf->lightmapNum >= 0 && numVerts)
		{
			getDimensions(surf - drawSurfaces, &newW, &newH);

			// Get a new position for this
			if ( !AllocLMBlock2( newW, newH, &newX, &newY ) ) {
				PrepareNewLightmap2();
				if ( !AllocLMBlock2( newW, newH, &newX, &newY ) ) {
					Error("Lightmap allocation failed for rechart\n" );
				}
			}

			multipliers[0] = (float)(newW - 1);
			multipliers[1] = (float)(newH - 1);

			// Move all verts to the new location
			for(j=0;j<numVerts;j++)
			{
				drawVert_t *vert = drawVerts + surf->firstVert + j;

				// Get normalized coordinates
				rescaledCoord[0] = ((vert->lightmap[0] * LIGHTMAP_WIDTH) - (float)surf->lightmapX - 0.5f) / divisors[0];
				rescaledCoord[1] = ((vert->lightmap[1] * LIGHTMAP_HEIGHT) - (float)surf->lightmapY - 0.5f) / divisors[1];

				// Transform to the recharted coordinates
				vert->lightmap[0] = ((rescaledCoord[0] * multipliers[0]) + (float)newX + 0.5f) / LIGHTMAP_WIDTH;
				vert->lightmap[1] = ((rescaledCoord[1] * multipliers[1]) + (float)newY + 0.5f) / LIGHTMAP_HEIGHT;
			}

			surf->lightmapNum = numLightmaps - MAP_BASIS_VECTORS;
			surf->lightmapX = newX;
			surf->lightmapY = newY;
			surf->lightmapWidth = newW;
			surf->lightmapHeight = newH;
		}
	}

	free(surfs);
}



/*
===============
CountLightmaps
===============
*/
void CountLightmaps( void ) {
	int			count;
	int			i;
	dsurface_t	*ds;

	qprintf ("--- CountLightmaps ---\n");
	count = 0;
	numLightTexels = 0;
	for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
		// see if this surface is light emiting
		ds = &drawSurfaces[i];
		if ( ds->lightmapNum > count ) {
			count = ds->lightmapNum;
		}
		if ( ds->lightmapNum >= 0 )
			numLightTexels += ds->lightmapWidth*ds->lightmapHeight;
	}

	count+=MAP_BASIS_VECTORS;
	numLightBytes = count * LIGHTMAP_WIDTH * LIGHTMAP_HEIGHT * 3;
	if ( numLightBytes > MAX_MAP_LIGHTING ) {
		Error("MAX_MAP_LIGHTING exceeded (%i > %i)", numLightBytes, MAX_MAP_LIGHTING);
	}

	qprintf( "%5i drawSurfaces\n", numDrawSurfaces );
	qprintf( "%5i lightmaps\n", count );
}
